#ifndef _DUAL_LINK_LIST_H_
#define _DUAL_LINK_LIST_H_

#include "Object.h"
#include "List.h"
#include "Exception.h"

namespace MySTL
{

template < typename T >
class DualLinkList : public List<T>
{
public:
	DualLinkList();
	~DualLinkList();

	bool insert(int n, const T& value);
	bool insert(const T& value);
	bool remove(int n);
	bool get(int n, T& value) const;
	T& get(int n);
	const T& get(int n) const;
	bool set(int n, const T& value);
	int length() const;
	int find(const T& value) const;
	void clear();

	T& operator [](int n);
	const T& operator [](int n) const;

	virtual bool move(int n, int step = 1);
	virtual bool end();
	virtual bool next();
	virtual bool pre();
	virtual T& current();

protected:
#pragma pack(4)
	struct Node : public Object
	{
		T value;
		Node* next;
		Node* pre;
	};
#pragma pack()
	Node* position(int n) const;
	Node* create_node();
	void destory_node(Node* node);

protected:
#pragma pack(4)
	mutable struct : public Object
	{
		char reserved[sizeof(T)];
		Node* next;
		Node* pre;
	} m_header;
#pragma pack()
	int m_length;
	Node* m_current;
	int m_step;
};

template < typename T >
DualLinkList<T>::DualLinkList()
{
	m_length = 0;
	m_header.next = NULL;
	m_header.pre = NULL;
	m_current = NULL;
	m_step = 1;
}

template < typename T >
DualLinkList<T>::~DualLinkList()
{
	clear();
}

template < typename T >
bool DualLinkList<T>::insert(int n, const T& value)
{
	bool ret = (n >= 0) && (n <= m_length);

	if (ret)
	{
		Node* node = create_node();
		if (NULL != node)
		{
			node->value = value;

			Node* current = position(n);

			node->next = current->next;
			current->next = node;
			node->pre = n > 0 ? current : NULL;
			if (NULL != node->next)
				node->next->pre = node;

			if (n == m_length)
			{
				m_header.pre = m_length > 0 ? m_header.pre->next : node;
			}

			++m_length;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to construct Node in bool DualLinkList<T>::insert(int n, const T& value)");
		}
	}

	return ret;
}

template < typename T >
bool DualLinkList<T>::insert(const T& value)
{
	return insert(m_length, value);
}

template < typename T >
bool DualLinkList<T>::remove(int n)
{
	bool ret = (n >= 0) && (n < m_length);

	if (ret)
	{
		Node* current = position(n);
		Node* toDel = current->next;

		current->next = toDel->next;
		if (NULL != toDel->next)
			toDel->next->pre = n > 0 ? current : NULL;

		if (n == m_length - 1)
		{
			m_header.pre = m_header.pre->pre;
		}

		if (m_current == toDel)
		{
			m_current = toDel->next;
		}

		--m_length;

		destory_node(toDel);
	}

	return ret;
}

template < typename T >
bool DualLinkList<T>::get(int n, T& value) const
{
	bool ret = (n >= 0) && (n < m_length);

	if (ret)
	{
		value = position(n)->next->value;
	}

	return ret;
}

template < typename T >
T& DualLinkList<T>::get(int n)
{
	if ((n >= 0) && (n < m_length))
	{
		return position(n)->next->value;
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index out of bounds in T& DualLinkList<T>::get(int n)");
	}
}

template < typename T >
const T& DualLinkList<T>::get(int n) const
{
	return const_cast<DualLinkList<T>*>(this)->get(n);
}

template < typename T >
bool DualLinkList<T>::set(int n, const T& value)
{
	bool ret = (n >= 0) && (n < m_length);

	if (ret)
	{
		position(n)->next->value = value;
	}

	return ret;
}

template < typename T >
int DualLinkList<T>::length() const
{
	return m_length;
}

template < typename T >
int DualLinkList<T>::find(const T& value) const
{
	int ret = -1;

	Node* current = m_header.next;

	for (int i = 0; i < m_length; ++i)
	{
		if (current->value == value)
		{
			ret = i;
			break;
		}
		current = current->next;
	}

	return ret;
}

template < typename T >
void DualLinkList<T>::clear()
{
	Node* current = position(0);
	while(current->next)
	{
		Node* toDel = current->next;
		current->next = toDel->next;
		if (NULL != toDel->next)
			toDel->next->pre = NULL;

		--m_length;

		destory_node(toDel);
	}

	m_current = NULL;
}

template < typename T >
T& DualLinkList<T>::operator [](int n)
{
	if ((n >= 0) && (n < m_length))
	{
		return position(n)->next->value;
	}
	else
	{
		THROW_EXCEPTION(IndexOutOfBoundsException, "Index out of bounds in T& DualLinkList<T>::operator [](int n)");
	}
}

template < typename T >
const T& DualLinkList<T>::operator [](int n) const
{
	return const_cast<DualLinkList<T>&>(*this)[n];
}

template < typename T >
bool DualLinkList<T>::move(int n, int step)
{
	bool ret = (n >= 0) && (n < m_length) && (step > 0);

	if (ret)
	{
		m_current = position(n)->next;
		m_step = step;
	}

	return ret;
}

template < typename T >
bool DualLinkList<T>::end()
{
	return m_current == NULL;
}

template < typename T >
bool DualLinkList<T>::next()
{
	int i = 0;
	for (; i < m_step && !end(); ++i)
	{
		m_current = m_current->next;
	}

	return i == m_step;
}

template < typename T >
bool DualLinkList<T>::pre()
{
	int i = 0;
	for (; i < m_step && !end(); ++i)
	{
		m_current = m_current->pre;
	}

	return i == m_step;
}

template < typename T >
T& DualLinkList<T>::current()
{
	if (!end())
	{
		return m_current->value;
	}
	else
	{
		THROW_EXCEPTION(InvalidOperationException, "Invalid operation in T& DualLinkList<T>::current()");
	}
}

template < typename T >
typename DualLinkList<T>::Node* DualLinkList<T>::position(int n) const
{
	Node* ret = reinterpret_cast<Node*>(&m_header);

	if (n <= m_length / 2)
	{
		for (int i = 0; i < n; ++i)
		{
			ret = ret->next;
		}
	}
	else
	{
		for (int i = 0; i < m_length - n + 1; ++i)
		{
			ret = ret->pre;
		}
	}

	return ret;
}

template < typename T >
typename DualLinkList<T>::Node* DualLinkList<T>::create_node()
{
	return new Node();
}

template < typename T >
void DualLinkList<T>::destory_node(Node* node)
{
	delete node;
}

}

#endif